/*
 * tabbporo.cpp
 *
 *  Created on: 03/02/2010
 *      Author: javier
 */
#include <iostream>
#include <string.h>
#include "tabbporo.h"

using namespace std;

TNodoABB::TNodoABB()
{
//Llama constructores otras clases, no modificar;
}

TNodoABB::TNodoABB( const TNodoABB &n )
{
	//Copiar(n);
	item = n.item;
	iz = n.iz;
	de = n.de;

}
/*
void
TNodoABB::Copiar( const TNodoABB & n)
{
	if( n != )
	{
		TNodoABB *aux = new TNodoABB();
		aux->item = n.item;

		aux->iz->nodo.Copiar(n.iz->nodo);
		aux->de->nodo.Copiar(n.de->nodo);
	}
	else aux = NULL;
}
*/
TNodoABB::~TNodoABB()
{
	Eliminar(*this);

}

void
TNodoABB::Eliminar(TNodoABB &n)
{
	if(n.iz.nodo != NULL)
	{
		Eliminar(*n.iz.nodo);
	}
	if(n.de.nodo != NULL)
	{
		Eliminar(*n.de.nodo);
	}
	n.iz.nodo=NULL;
	n.de.nodo=NULL;
	item.~TPoro();
}

TNodoABB &
TNodoABB::operator=( const TNodoABB &n )
{
	//Copiar(n);
	if( this != &n )
	{
		item = n.item;
		iz = n.iz;
		de = n.de;
	}
	return *this;
}

// ######## COMIENZO TABBPORO ########

TABBPoro::TABBPoro()
{
	nodo = NULL;
}


TABBPoro::TABBPoro(const TABBPoro &p)
{
    if( p.nodo!=NULL )
    {
        nodo = new TNodoABB(*p.nodo);
    }
    else
    {
        nodo = NULL;
    }
}


TABBPoro::~TABBPoro()
{
	if( nodo != NULL )
	{
		delete nodo;
		nodo = NULL;
	}

	//EliminarABB(this->nodo);
	//nodo = NULL;
}
/*
void
TABBPoro::EliminarABB(TNodoABB &n)
{
	if(n.iz.nodo!=NULL)
	{
		n.iz.EliminarABB()
	}
	if(n.de.nodo!=NULL)
	{
		Eliminar(n.de.nodo);
	}
	n.iz.nodo=NULL;
	n.de.nodo=NULL;
	delete item;
}
*/
TABBPoro &
TABBPoro::operator=(const TABBPoro &p)
{
        if(this!=&p)
        {
			this->~TABBPoro();
			if(p.nodo!=NULL)
			{
				nodo=new TNodoABB(*(p.nodo));
				//*nodo=*(p.nodo);
			}
        }

	return *this;
}

bool
TABBPoro::operator==( const TABBPoro &p)
{
	bool igual = false;

	if( this->Altura() == p.Altura() )
	{
		//igual = CompararABB( this->nodo, p.nodo);
		if ( this->Inorden() == p.Inorden() ) igual = true;

	}

	return igual;
}
/*
bool
TABBPoro::CompararABB( const TNodoABB &a, const TNodoABB &b)
{
	if( a != NULL && b != NULL )
	{
		if( a.item != b.item )

		aux->iz->nodo(n.iz->nodo);
		aux->de->nodo.CopiarABB(n.de->nodo);
	}
	else aux = NULL; // Caso base, Altura?

}*/

bool
TABBPoro::EsVacio() const
{
	bool vacio = true;

	if( nodo != NULL ) vacio = false;

	return vacio;
}

bool
TABBPoro::Insertar( TPoro &p)
{
	bool inserted = false;

	if( nodo == NULL )
	{
		nodo = new TNodoABB;
		nodo->item = p;
		inserted = true;
	}
	else if ( p.Volumen() == nodo->item.Volumen() ) // Lo ponemos antes para que no prosiga la ejecucion.
	{
		inserted = false;
	}
	else
	{
		if( p.Volumen() < nodo->item.Volumen() )
			inserted = nodo->iz.Insertar(p);
		else  inserted = nodo->de.Insertar(p);
	}

	return inserted;
}

bool
TABBPoro::Borrar(const TPoro &p )
{
	bool borrado;

	if( nodo == NULL )
	{
		borrado = false;
	}
	else if( nodo->item.Volumen() < p.Volumen())
	{
		if (nodo->de.Borrar(p))
			borrado = true;
	}
	else if( nodo->item.Volumen() > p.Volumen())
	{
		if(nodo->iz.Borrar(p))
			borrado = true;
	}
	else // El item del nodo es igual al poro buscado;
	{
		TNodoABB *aux;

		if( nodo->iz.nodo == NULL )
		{
			aux = nodo;
			nodo = nodo->de.nodo;
			aux->de.nodo = NULL;
			delete aux;
			aux = NULL;
			borrado = true;
		}
		else if ( nodo->de.nodo == NULL )
		{
			aux = nodo;
			nodo = nodo->iz.nodo;
			aux->iz.nodo = NULL;
			delete aux;
			aux = NULL;
			borrado = true;
		}
		else // Caso de que tenga dos hijos.
		{
			//Procedimiento para hacer el intercambio en el borrado.
			this->IntercambiarBorrar();
			borrado = true;
		}
	}
	return borrado;
}

void
TABBPoro::IntercambiarBorrar( )
{
	TNodoABB *ant, *post, *nodoactual;

	nodoactual = nodo;
	ant = nodo;
	post = nodo->iz.nodo;

	if(post->de.nodo == NULL)
	{
		nodoactual->item = post->item;
		nodoactual->iz.nodo = post->iz.nodo;		
	}
	
	else {
		while( post->de.nodo != NULL ) // Buscamos el mayor de la izquierda, por eso hacemos de.
		{
			ant = post;
			post = post->de.nodo;
		}
		ant->de.nodo = post->iz.nodo;
		nodoactual->item = post->item;
	}
	
	delete post;
	ant = NULL;
	post = NULL;
	nodoactual = NULL;
}

bool
TABBPoro::Buscar( const TPoro &p ) const
{
	bool found = false;

	if( nodo == NULL )
	{
		found = false;
	}
	else
	{
		if( nodo->item.Volumen() == p.Volumen() )
		{
			found = true;
		}
		else
		{
			if( nodo->item.Volumen() > p.Volumen() )
				found = nodo->iz.Buscar(p);

			else found = nodo->de.Buscar(p);
		}
	}
	return found;

}


TPoro
TABBPoro::Raiz() const
{
	if( this->nodo != NULL ) return nodo->item;
	else return TPoro();
}

int
TABBPoro::Altura() const
{
	int a1, a2;

	if( this->nodo != NULL )
	{
		a1 = this->nodo->iz.Altura();
		a2 = this->nodo->de.Altura();
		if(a1>a2)
			return (1+a1);
		else
			return (1+a2);
	}
	else return 0;

}

int
TABBPoro::Nodos() const
{
	int n1,n2;

	if( this->nodo != NULL )
	{
		n1 = this->nodo->iz.Nodos();
		n2 = this->nodo->de.Nodos();
		return ( 1+n1+n2 );
	}
	else return 0;
}

int
TABBPoro::NodosHoja()
{
	int nhojas;

	if(this->nodo == NULL)
	{
		nhojas = 0;
	}
	else if( nodo->iz.nodo == NULL && nodo->de.nodo == NULL )
	{
		nhojas = 1;
	}
	else
	{
		nhojas = nodo->iz.NodosHoja() + nodo->de.NodosHoja();
		/*if (this->nodo->iz == NULL && this->nodo->de != NULL)
			return (this->nodo->de.NodosHoja());
		if (this->nodo->iz != NULL && this->nodo->de == NULL)
					return (this->nodo->iz.NodosHoja());
		else
			return(this->nodo->iz.NodosHoja()+this->nodo->de.NodosHoja());*/
	}

	return nhojas;
}


TABBPoro
TABBPoro::operator+(const TABBPoro &p)
{
	TABBPoro resultado;
	
	resultado=*this;
	TVectorPoro arbolderecho;
	arbolderecho = p.Niveles();
	for(int i=1; arbolderecho.Cantidad()>=i; i++)
	{
		resultado.Insertar(arbolderecho[i]);
	}
	
	return resultado;
}

TABBPoro
TABBPoro::operator-(const TABBPoro &p)
{
	TABBPoro resultado;
	
	resultado=*this;
	TVectorPoro vaux;
	vaux = p.Niveles();

	for( int i = 1; i <= vaux.Longitud() ; i++)
	{
		if(resultado.BuscarpaRestar(vaux[i]))
			resultado.Borrar(vaux[i]);
	}

	return resultado;
	/*
	TABBPoro resultado;

	TVectorPoro arbolizquierdo;
	arbolizquierdo = this->Niveles();
	for(int i=1; arbolizquierdo.Cantidad()>=i; i++)
	{
		if(!p.Buscar(arbolizquierdo[i]))
		{
				resultado.Insertar(arbolizquierdo[i]);
		}
	}
	*/
	return resultado;
}

bool
TABBPoro::BuscarpaRestar(const TPoro &p ){

	bool found = false;

	if( nodo == NULL )
	{
		found = false;
	}
	else
	{
		if( nodo->item.Volumen() == p.Volumen() && (strcmp(nodo->item.Color(),p.Color())==0) )
		{
			found = true;

		}
		else
		{
			if( nodo->item.Volumen() > p.Volumen() )
				found = nodo->iz.Buscar(p);

			else found = nodo->de.Buscar(p);
		}
	}
	return found;
}

TVectorPoro
TABBPoro::Inorden() const
{
	int i = 1;
	TVectorPoro v( this->Nodos());
	this->InordenAux(v, i);
	return v;
}

void
TABBPoro::InordenAux( TVectorPoro &v, int &i) const
{
	if( nodo != NULL )
	{
		nodo->iz.InordenAux(v,i);
		v[i] = nodo->item;
		i++;
		nodo->de.InordenAux(v,i);
	}
}

TVectorPoro
TABBPoro::Preorden() const
{
	int i = 1;
	TVectorPoro v(this->Nodos());
	this->PreordenAux(v, i);
	return v;
}

void
TABBPoro::PreordenAux( TVectorPoro &v, int &i) const
{
	if( nodo != NULL )
	{
		v[i] = nodo->item;
		i++;
		nodo->iz.PreordenAux(v,i);
		nodo->de.PreordenAux(v,i);
	}
}

TVectorPoro
TABBPoro::Postorden() const
{
	int i = 1;
	TVectorPoro v(this->Nodos());
	this->PostordenAux(v, i);
	return v;
}

void
TABBPoro::PostordenAux( TVectorPoro &v, int &i) const
{
	if( nodo != NULL )
	{
		nodo->iz.PostordenAux(v,i);
		nodo->de.PostordenAux(v,i);
		v[i] = nodo->item;
		i++;
	}
}


TVectorPoro
TABBPoro::Niveles() const
{
	TVectorPoro v(Nodos());
	TColaABBPoro cola;
	TABBPoro* aux;

	int i=0;

	if( !this->EsVacio() )
	{
		//TABBPoro* auxthis = this;
		cola.Encolar( (TABBPoro*) this);
		
		while(!cola.EsVacia())
		{
			aux=cola.Cabeza();
			i++;
			v[i]=aux->nodo->item;
			cola.Desencolar();
			if(!aux->nodo->iz.EsVacio())
			{
				TABBPoro *izhijo = new TABBPoro(aux->nodo->iz);
				cola.Encolar(izhijo);
			}
			if(!aux->nodo->de.EsVacio())
			{
				TABBPoro *dehijo = new TABBPoro(aux->nodo->de);
				cola.Encolar(dehijo);
			}
		}
	}
	aux = NULL;

	return v;
}

ostream &
operator<<(ostream &os, const TABBPoro &arb)
{
	TVectorPoro v = arb.Niveles();
	os << v;

	return os;
}
